"""
给定一个未排序的整数数组，找出最长连续序列的长度。

要求算法的时间复杂度为 O(n)。
输入: [100, 4, 200, 1, 3, 2]
输出: 4
解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。
使用dict加快搜索，计算左右是否存在，然后将左右写入dictionary中
"""


class Solution(object):
    def longestConsecutive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        d = {}
        ans = 0
        for i in nums:
            if i not in d:
                left = d.get(i-1, 0)
                right = d.get(i+1, 0)
                length = left + right + 1
                ans = max(ans, length)
                d[i] = length
                d[i-left] = length
                d[i+right] = length
        return ans